package tree;

import java.util.HashMap;
import java.util.Map;

/**
 * @author dx
 * @version 1.0
 * @date 2022/5/9 10:11
 * @description:   输入某二叉树的前序遍历贺中序遍历结果，重建该二叉树
 */

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){this.val = x;}
}


public class rebuild_tree {
    public static void main(String[] args){
        int []preorder = new int[]{1,2,4,7,3,5,6,8};
        int []inorder = new int[]{4,7,2,1,5,3,8,6};
        TreeNode new_root = new TreeNode(-1);
        new_root = new soslution().buildTree(preorder,inorder);
        print_inorder(new_root);
    }

    public static void print_inorder(TreeNode node){
        if(node == null){
            return;
        }
        print_inorder(node.left);
        System.out.println(node.val);
        print_inorder(node.right);

    }

}

class soslution{
    Map<Integer,Integer> indexMap;

    public  TreeNode myBuildTree(int[] preorder,int[] inorder,int preorder_left,int preorder_right,int inorder_left){
        if(preorder_left > preorder_right){
            return null;
        }
        int preorder_root = preorder_left;

        //在中序的数组中 定义到根节点的位置
        int inorder_root = indexMap.get(preorder[preorder_root]);

        //先把根节点创建出来
        TreeNode root = new TreeNode(preorder[preorder_root]);

        //得到左子树中的节点数目，中序根节点位置 - 中序开始的位置
        int size_left_subtree = inorder_root - inorder_left;
        //递归地构造左子树，并连接到根节点
        root.left = myBuildTree(preorder,inorder,preorder_left + 1,preorder_left + size_left_subtree,inorder_left);
        //递归地构造右子树，并连接到根节点
        root.right = myBuildTree(preorder,inorder,preorder_left+size_left_subtree+1,preorder_right,inorder_root+1);
        return root;
    }
    public  TreeNode buildTree(int[] preorder,int[] inorder){
        int n = preorder.length;
        //构建哈希映射，快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for(int i = 0; i < n;i++){
            indexMap.put(inorder[i],i);
        }
        return myBuildTree(preorder,inorder,0,n-1,0);
    }
}